With the beginning of its development, computer technology broadly implements graph theory. Every computer network could be viewed as a graph with certain properties including a plurality of computer devices as nodes. In software applications, graph theory provides various algorithms for data processing. The automation of an increasing number of business processes is one of the most challenging areas for the development of computer technology. In this field, graph theory helps with efficient solutions of numerous problems.
For example, bill of materials (BOM) is commonly used by manufacturers to describe raw materials, sub-assemblies, intermediate assemblies, sub-components, components and parts, and the quantities of each needed to manufacture a final product. BOMs are exchanged between manufacturers and suppliers and are used for planning and controlling the process of producing final product. In general, BOMs could be described as a directed acyclic graph with the final product as a root vertex, and a plurality of leaf vertices representing the raw materials or components necessary to produce the final product.
To each vertex or component in a BOM directed graph could be assigned a low-level code, e.g., a number, to facilitate the material requirements planning. When a bill of materials is changed, it has to be checked if BOM recursion occurs. Further, the low-level codes need to be recalculated when the added vertices and edges violate the previously established order. This is important in order to keep a consistent relationships between the materials. For large and complex BOMs, these tasks are time consuming for the currently applied algorithms, and may lead to system performance problems.
There are other business applications that apply the same concept of directed graphs with assigned low-level codes to the nodes. In addition to BOM relations, a directed graph could contain edges that represent material or component replacement, material transportation from one site to another, etc.